package sort;

/**
 * @description: TODO
 * @author: mayunfei
 * @date: 2024/12/10 7:44
 */
public class QuickSort implements ArraySort{

    @Override
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private void sort(int[] nums, int l, int r) {
        if (l < r) {
            int key = nums[l];
            int i = l;
            int j = r;
            while (i < j) {
                while (i < j && nums[j] > key) {
                    j--;
                }
                if (i < j) {
                    nums[i] = nums[j];
                    i++;
                }
                while (i < j && nums[i] < key) {
                    i++;
                }
                if (i < j) {
                    nums[j] = nums[i];
                    j--;
                }
            }
            nums[i] = key;
            sort(nums, l, i - 1);
            sort(nums, i + 1, r);
        }
    }
}
